class ShellSort():
    def __init__(self) -> None:
        self.count = 0
    
    def sort(self,ls):
        gap = len(ls)//2
        while gap>0:
            i = gap
            while i<len(ls):
                j = i
                # 每隔gap个进行插入排序
                while j>=gap and ls[j]<ls[j-gap]:
                    ls[j],ls[j-gap]=ls[j-gap],ls[j]
                    j-=gap
                    self.count +=1
                i+=1
            gap//=2
    # 判断是否有序
    def isSorted(self,ls):
        for i in range(1,len(ls)):
            if ls[i]<ls[i-1]:
                return False
        return True

